1. Field of the Invention
The present invention is directed to a system for establishing a transmission sequence by which terminals in a wireless network communicate. In particular, the invention is directed to a system which generates a matrix identifying which terminals are to transmit and/or receive data, and which uses entries in that matrix to establish a transmission sequence with a reduced number of one-slot transition turnarounds in the wireless terminals. The invention has particular utility in connection with the medium access control protocol for wireless ATM networks, in which the transmission sequence for wireless terminals is defined by slots in a control data frame.
2. Description of the Related Art
ATM (xe2x80x9casynchronous transfer modexe2x80x9d) is a protocol which was developed to address problems associated with transmitting multimedia data between networked devices. In particular, ATM networks are systems that negotiate and establish transmission parameters (e.g., bandwidth) prior to connecting two networked devices, xe2x80x9cpacketizexe2x80x9d different types of data (e.g., video and audio data) into cells based on the established transmission parameters, and then multiplex these cells so that they can be transmitted over a single communication line to a receiving device. The receiving device then checks the transmitted data for errors and, if any are present, requests retransmission of the data by the transmitting device.
Traditionally, ATM networks were wire-based, meaning that devices therein were interconnected using fiber optic cables or the like. Recently, however, wireless ATM networks have been developed which replace at least some of these fiber optic cables with point-to-point wireless connections, such as radio-frequency (xe2x80x9cRFxe2x80x9d) and infrared (xe2x80x9cIRxe2x80x9d) links. A wireless ATM network of this type is described in U.S. patent application Ser. No. 08/770,024, entitled xe2x80x9cMedium Access Control (MAC) Protocol For Wireless ATMxe2x80x9d, the contents of which are hereby incorporated by reference into the subject application as if set forth herein in full.
In detail, the foregoing U.S. patent application describes a communications protocol (i.e., the MAC protocol) for wireless ATM networks, which increases network quality of service, particularly in terms of allocated bandwidth, by first reserving and then scheduling resources required for data transmission. FIGS. 1 and 2 show different configurations of wireless ATM networks on which the MAC protocol is implemented. Specifically, FIG. 1 shows a xe2x80x9cbase stationxe2x80x9d configuration, in which base stations (or xe2x80x9cBSsxe2x80x9d) control communications among various wireless terminals (or xe2x80x9cWTsxe2x80x9d), and FIG. 2 shows a so-called xe2x80x9cad-hocxe2x80x9d configuration in which one of the wireless terminals is assigned the task of controlling communications (i.e., the central controller, or xe2x80x9cCCxe2x80x9d).
In both the base station and ad-hoc configurations, communications among the various wireless terminals are effected via a time-slot based control data frame (xe2x80x9cCDFxe2x80x9d). As shown in FIG. 3, this CDF includes both a control phase 1 and a data phase 2, each of which includes plural slots 4 for transmitting requests or data to/from various wireless terminals. Specifically, in the control phase, a wireless terminal sends a request to a scheduler in a base station or central controller via a control slot in the CDF. Generally speaking, this is a request for permission for the wireless terminal to transmit data packet(s) to another wireless terminal during the data phase of a next CDF. The scheduler gathers all such requests from the wireless terminals, and then allocates available data slots in the data phase of the next CDF to appropriate pairs of wireless terminals. That is, the scheduler allocates each data slot to a transmit/receive terminal pair, such that the transmitting terminal is permitted to send data in a particular data slot and the receiving terminal is permitted to receive the data from that data slot. Once these allocations are made, they are broadcast to the various wireless terminals, thereby informing each wireless terminal which data slots in the next CDF it can use to transmit/receive data.
In MAC-based wireless ATM networks of the type described above, all wireless terminals typically operate on the same frequency. As a result, it is not possible to switch a wireless terminal from a transmitting mode to a receiving mode without some time delay. This delay, which is commonly referred to as the minimum transceiver turnaround time (xe2x80x9cMINTATxe2x80x9d), needs to be taken into account when determining the transmission sequence by which wireless terminals in the network communicate. Specifically, in order to reduce a degradation in network performance resulting from the MINTAT, slots in the CDF should be allocated so that each wireless terminal has enough time (at least the MINTAT) to switch from its transmitting mode to its receiving mode without adding additional delay into the network. To this end, when designing a transmission sequence, it is thus desirable to avoid situations where a wireless terminal changes from its transmitting mode to its receiving mode in adjacent slots of a CDF. This xe2x80x9cone-slot transition turnaroundxe2x80x9d (or xe2x80x9cOTTxe2x80x9d) as it is called, results in additional networks delays and, therefore, should be avoided (or minimized) whenever possible.
Conventional systems reduce the number of OTTs during a transmission sequence by using dynamic programming or conventional back-tracking techniques, such as the xe2x80x9cbranch and boundxe2x80x9d method. In brief, the branch and bound method is performed by generating a plurality of groups of transmission sequences for a single CDF. These groups are then divided into two sub-groups, from which the better of the two sub-groups (i.e., the sub-group which includes the fewest OTTs) is selected. Thereafter, the selected sub-group is then divided into two sub-sub-groups, from which the better of the two is selected, and so on until the best transmission sequence is selected. The problem with methods of this type is that they are computationally intensive, and become even more so as the number of communications per transmission sequence increase.
In response to the deficiencies of the foregoing methods, heuristic methods were developed for establishing a transmission sequence with relatively few OTTs. However, these heuristic methods have proven unsatisfactory for a number of reasons. For example, conventional heuristic methods have, heretofore, been unable to reduce the number of OTTs per transmission sequence to a satisfactory level. Moreover, these methods are often difficult to implement and can be computationally intensive.
Accordingly, there exists a need for a system which establishes a transmission sequence for terminals in a wireless network, which reduces the number of OTTs per transmission sequence, and which is less computationally intensive than its conventional counterparts. In particular, there exists a need for a system which allocates slots in a control data frame of a wireless ATM network running the MAC protocol so as to achieve these and other advantages.
The present invention addresses the foregoing needs by allocating slots in a CDF based on entries in a transmit/receive matrix. In particular, the invention generates a transmit/receive matrix which includes rows of terminals and columns of terminals. At each row/column nexus is an entry which defines whether communications are to be effected between a pair of terminals corresponding to that entry. The invention uses these entries to select the order in which pairs of terminals are to appear in the CDF. By establishing a transmission sequence in this manner, the invention is able to reduce the number of OTTs to two or less in most cases, and to do so using relatively simple calculations. Thus, unlike its conventional counterparts, the invention is able to reduce network degradation relatively easily.
Thus, according to one aspect, the present invention is a system (e.g., a method, an apparatus, and computer-executable process steps) for establishing a transmission sequence for effecting communications between plural terminals in a wireless network. This transmission sequence is defined by a CDF comprised of plural slots, each of which can be allocated for communication between one pair of the plural terminals. In operation, the system begins by generating a transmit/receive matrix for the plural terminals in the wireless network. This transmit/receive matrix includes plural rows and plural columns, where each of the plural rows corresponds to a terminal and each of the plural columns corresponds to a same or different terminal. At each row/column nexus, the transmit/receive matrix includes an entry which indicates whether communications are to be effected between a pair of terminals that corresponds thereto. Slots in the CDF are then allocated between pairs of the plural terminals based on these entries in the transmit/receive matrix.
According to another aspect, the invention is a system for using a transmit/receive matrix to allocate data slots in a control data frame to pairs of terminals, where the transmit/receive matrix is comprised of plural rows and plural columns. Each of the plural rows corresponds to a terminal and each of the plural columns corresponds to a terminal. The transmit/receive matrix includes an entry at each row/column nexus, each entry comprising either a one to indicate that communications are to be effected between a pair of the terminals that corresponds to the entry or a zero to indicate that communications are not to be effected between a pair of terminals that corresponds to the entry.
In operation, the system (A) selects an entry (i0,j0) in the transmit/receive matrix which has at least one of a minimum non-zero row sum and a minimum non-zero column sum, where xe2x80x9cixe2x80x9d represents a row number and xe2x80x9cjxe2x80x9d represents a column number, and (B) allocates a first available data slot in the control data frame to a pair of terminals that corresponds to entry (i0,j0) in the transmit/receive matrix. The system then (C) searches row i0 for non-zero entries with increasing column sums, (D) allocates succeeding data slots in the control data frame to pairs of terminals that have non-zero entries in row i0 with increasing column sums, and (E) sets, to zero, non-zero entries in row i0. Next, the system (F) searches column jL for a non-zero entry with a minimum row sum, where column jL comprises a last column in row i0 having a highest non-zero column sum.
In a case that a non-zero entry with a minimum row sum is found in column jL the system (i) allocates a next succeeding data slot in the control data frame to a pair of terminals that has a non-zero entry in column jL with a minimum row sum, (ii) sets, to zero, the non-zero entry in column jL with the minimum row sum, and (iii) repeats at least steps (B) through (F) above substituting the non-zero entry in column jL with the minimum row sum for entry (i0,j0). On the other hand, in a case that a non-zero entry with a minimum row sum is not found in column jL, the system (i) masks a row having a value jL and a column having a value i0 to produce a masked transmit/receive matrix, and (ii) determines whether the masked transmit/receive matrix includes an entry (i1,j1) which has at least one of a minimum non-zero row sum and a minimum non-zero column sum.
In a case that the masked transmit/receive matrix includes an entry (i1,j1) with at least one of a minimum non-zero row sum and a minimum non-zero column sum, the system repeats at least steps (B) through (F) above substituting entry (i1,j1) for entry (i0j0). On the other hand, in a case that the masked transmit/receive matrix does not include an entry (i1,j1) with at least one of a minimum non-zero row sum and a minimum non-zero column sum, the system (i) unmasks row jL and column i0 to produce an unmasked transmit/receive matrix, (ii) selects an entry (i2,j2) from the unmasked transmit/receive matrix, and (iii) repeats at least steps (B) through (F) above substituting entry (i2,j2) for entry (i0,j0) and using the unmasked transmit/receive matrix.
By virtue of the foregoing steps, the invention is able to allocate data slots in the CDF so as to produce, in most cases, a maximum of two one-slot transition turnarounds per control data frame. This is a significant advantage over its conventional counterparts, which have heretofore been unable to achieve similar results without the use of algorithms that are significantly more computationally intensive than the foregoing system.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiments thereof in connection with the attached drawings.